§1.1 Field of the Invention
The present invention concerns IP networks. In particular, the present invention concerns failure recovery using rerouting schemes that determine backup ports within an IP network.
§1.2 Background Information
The Internet has evolved to a global information platform that supports numerous applications ranging from online shopping to worldwide business-related and science-related activities. For such a critical infrastructure, survivability is a stringent requirement in that services interrupted by equipment failures must be recovered as quickly as possible. Typically, a recovery time of tens of milliseconds satisfies most requirements (e.g., SDH/SONET automatic protection switching (“APS”) is completed within 50 ms). At the same time, it is desired that failure recovery schemes have low complexity and do not reserve redundant bandwidth.
Network failures can be caused by a variety of reasons such as fiber cut, interface malfunctioning, software bugs, misconfiguration and attacks. Despite continuous technological advances, failures have occurred even in well maintained networks.
An important issue of failure recovery is how to set up a new path to replace a damaged one. The main approaches used by today's IP networks are route recalculation and lower layer protection. Each is introduced below.
Routing protocols (such as open shortest path first (“OSPF”) and intermediate system to intermediate system intra-domain routing (“IS-IS”) are typically designed to perform failure advertising, route recalculation and routing table update to recover from failures. Although these mechanisms can deal with various types of failures, the time for the recovery process can easily reach seconds. Such delays can lead to long service disruptions, dropped packets, latency, etc., to an extent unacceptable for certain applications (such as stock trading systems, for example).
On the other hand, lower layer protection achieves fast recovery by establishing backup connections in advance (e.g., a time slot channel). These previously established backup connections are used to quickly replace damaged connections. In this case, the IP layer can be protected from failures without any modifications on the routing tables. However, this type of approach reserves redundant bandwidth (such as redundant links or channels on links, redundant ports, etc.) for the backup connections. More importantly, relying on lower layer protection means the IP layer is not independent in term of survivability. From this point of view, an original objective of packet switching—to design a highly survivable network where packet forwarding in each router is adaptive to the network status—is still not fully achieved.
The framework of IP fast rerouting (“IPFRR”) is described in a recent draft of Internet Engineering Task Force (“IETF”). (See, e.g., M. Shand and S. Bryant, “IP fast reroute framework,” Internet-Draft, October 2005. (Online) available at http://www.ietf.org/intemet-drafts/draftietf-rtgwg-ipfrr-framework-04.txt.) Basically, IPFRR lets a router maintain (the identity of) a backup port for each destination and use the backup port to forward packets when the primary port fails. Since the backup ports are determined in advance and do not occupy or otherwise reserve redundant bandwidth, IPFRR can achieve fast failure recovery with great cost-efficiency. IPFRR and the following presume that failure detection has already occurred (e.g., using a known or proprietary techniques).